package org.hhchat.leetcode.sort;

/**
 * Created this one by HMH on 2017/5/29.
 * 要点，排序标准：s1+s2 < s2+s1
 */
public class code179 {
    public static class Solution {
        public String largestNumber(int[] nums) {
            quickSort(nums, 0, nums.length - 1);
            StringBuilder stringBuilder = new StringBuilder();
            if(nums.length == 0 || nums[0] == 0){
                return "0";
            }
            for (int i : nums) {
                stringBuilder.append(i);
            }
            return stringBuilder.toString();
        }

        public int compare(int a, int b) {
            String aStr = String.valueOf(a);
            String bStr = String.valueOf(b);
            String ab = aStr + bStr;
            String ba = bStr + aStr;
            return ab.compareTo(ba);
        }

        public void quickSort(int[] nums, int l, int h) {
            if (l <= h) {
                int mid = partition(nums, l, h);
                quickSort(nums, l, mid - 1);
                quickSort(nums, mid+1, h);
            }
        }

        public int partition(int[] nums,int l,int h) {
            int j=l;
            int key = nums[l];
            for(int i =l+1;i<=h;i++) {
                if (compare(nums[i],key)>0) {
                    swap(nums, ++j, i);
                }
            }
            swap(nums,j, l);
            return j;
        }

        public void swap(int[] nums,int l, int h) {
            int temp = nums[l];
            nums[l] = nums[h];
            nums[h] = temp;
        }
    }

    public static void main(String[] args){
        int[] nums = new int[]{3, 30, 34, 5, 9};
        Solution solution = new Solution();
        System.out.println(solution.largestNumber(nums));
    }
}

//    3Line solution

//    public String largestNumber(int[] num) {
//        String[] array = Arrays.stream(num).mapToObj(String::valueOf).toArray(String[]::new);
//        Arrays.sort(array, (String s1, String s2) -> (s2 + s1).compareTo(s1 + s2));
//        return Arrays.stream(array).reduce((x, y) -> x.equals("0") ? y : x + y).get();
//    }